package study1;

import java.util.Arrays;
import java.util.List;

public class PreorderTraversalTest {
    public static void main(String[] args) {
        // 构建测试用的二叉树
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        PreorderTraversal.TreeNode root = new PreorderTraversal.TreeNode(1);
        root.left = new PreorderTraversal.TreeNode(2);
        root.right = new PreorderTraversal.TreeNode(3);
        root.left.left = new PreorderTraversal.TreeNode(4);
        root.left.right = new PreorderTraversal.TreeNode(5);

        PreorderTraversal traversal = new PreorderTraversal();

        // 测试1: 递归方法（直接打印）
        System.out.println("测试1: 递归方法（直接打印）");
        traversal.preOrder(root);
        System.out.println("\n----------------------------------");
        /*测试1: 递归方法（直接打印）
          1 2 4 5 3
          ----------------------------------*/

        // 测试2: 递归方法（返回集合）
        System.out.println("测试2: 递归方法（返回集合）");
        List<Integer> result2 = traversal.preorderTraversal(root);
        System.out.println("结果: " + result2);
        System.out.println("预期: [1, 2, 4, 5, 3]");
        System.out.println("匹配: " + result2.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试2: 递归方法（返回集合）
          结果: [1, 2, 4, 5, 3]
          预期: [1, 2, 4, 5, 3]
          匹配: true
          ----------------------------------*/

        // 测试3: 迭代显式栈方法1
        System.out.println("测试3: 迭代显式栈方法1");
        List<Integer> result3 = traversal.preorderTraversal2(root);
        System.out.println("结果: " + result3);
        System.out.println("匹配: " + result3.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试3: 迭代显式栈方法1
          结果: [1, 2, 4, 5, 3]
          匹配: true
          ----------------------------------*/

        // 测试4: 迭代显式栈方法2（中序模板修改版）
        System.out.println("测试4: 迭代显式栈方法2（中序模板修改版）");
        List<Integer> result4 = traversal.preorderTraversal3(root);
        System.out.println("结果: " + result4);
        System.out.println("匹配: " + result4.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试4: 迭代显式栈方法2（中序模板修改版）
          结果: [1, 2, 4, 5, 3]
          匹配: true
          ----------------------------------*/

        // 测试5: 迭代显式栈方法3（统一写法）
        System.out.println("测试5: 迭代显式栈方法3（统一写法）");
        List<Integer> result5 = traversal.preorderTraversal4(root);
        System.out.println("结果: " + result5);
        System.out.println("匹配: " + result5.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试5: 迭代显式栈方法3（统一写法）
          结果: [1, 2, 4, 5, 3]
          匹配: true
          ----------------------------------*/

        // 测试6: Morris遍历
        System.out.println("测试6: Morris遍历");
        List<Integer> result6 = traversal.preorderTraversal5(root);
        System.out.println("结果: " + result6);
        System.out.println("匹配: " + result6.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试6: Morris遍历
          结果: [1, 2, 4, 5, 3]
          匹配: true
          ----------------------------------*/

        // 测试7: 颜色标记法
        System.out.println("测试7: 颜色标记法");
        List<Integer> result7 = traversal.preorderTraversal6(root);
        System.out.println("结果: " + result7);
        System.out.println("匹配: " + result7.equals(Arrays.asList(1, 2, 4, 5, 3)));
        System.out.println("----------------------------------");
        /*测试7: 颜色标记法
            结果: [1, 2, 4, 5, 3]
            匹配: true
            ----------------------------------*/

        // 边界测试：空树
        System.out.println("边界测试：空树");
        List<Integer> emptyResult = traversal.preorderTraversal(null);
        System.out.println("结果: " + emptyResult + " (应为空列表)");
        System.out.println("匹配: " + (emptyResult.size() == 0));
        System.out.println("----------------------------------");
        /*边界测试：空树
            结果: [] (应为空列表)
            匹配: true
            ----------------------------------*/

        // 边界测试：单节点树
        System.out.println("边界测试：单节点树");
        PreorderTraversal.TreeNode singleNode = new PreorderTraversal.TreeNode(10);
        List<Integer> singleResult = traversal.preorderTraversal(singleNode);
        System.out.println("结果: " + singleResult);
        System.out.println("匹配: " + singleResult.equals(Arrays.asList(10)));
        /*边界测试：单节点树
            结果: [10]
            匹配: true*/
    }
}